package com.chj.acwing.zhou211;

import java.util.Arrays;
import java.util.Comparator;

public class Code02_BestTeamWithNoConflicts {

	public static class Envelope {
		public int l;
		public int h;

		public Envelope(int weight, int hight) {
			l = weight;
			h = hight;
		}
	}

	public static class EnvelopeComparator implements Comparator<Envelope> {
		@Override
		public int compare(Envelope o1, Envelope o2) {
//			return o1.l != o2.l ? o1.l - o2.l : o2.h - o1.h;
			if (o1.l != o2.l) {
				if (o1.l > o2.l) {
					return 1;
				} else if (o1.l < o2.l) {
					return -1;
				} else {
					return 0;
				}

			} else {

				if (o1.h > o2.h) {
					return 1;
				} else if (o1.h < o2.h) {
					return -1;
				} else {
					return 0;
				}
			}
		}
	}

	public static Envelope[] getSortedEnvelopes(int[][] matrix) {
		Envelope[] res = new Envelope[matrix.length];
		for (int i = 0; i < matrix.length; i++) {
			res[i] = new Envelope(matrix[i][0], matrix[i][1]);
		}
		Arrays.sort(res, new EnvelopeComparator());
		return res;
	}

	public int bestTeamScore(int[] scores, int[] ages) {

		if (scores == null || scores.length == 0 || ages == null || ages.length == 0) {
			return 0;
		}

		if (scores.length == 1) {
			return scores[0];
		}

		int len = scores.length;

		int[][] combine = new int[len][2];
		for (int i = 0; i < len; i++) {
			combine[i][0] = ages[i];
			combine[i][1] = scores[i];
		}

		Envelope[] envelopes = getSortedEnvelopes(combine);

//		Arrays.sort(combine, (o1, o2) -> {
//			return o1[0] != o2[0] ? o1[0] - o2[0] : o1[1] - o2[1];
//		});

		int[] dp = new int[len];
		int ans = 0;
		for (int i = 0; i < len; i++) {
			dp[i] = envelopes[i].h;
			for (int j = 0; j < i; j++) {
				if (envelopes[j].h <= envelopes[i].h) {
					dp[i] = Math.max(dp[i], envelopes[i].h + dp[j]);
				}
			}
		}

		for (int i = 0; i < len; i++) {
			ans = Math.max(ans, dp[i]);
		}
		return ans;
	}

}
